GATE IT 2007
Q11.
Consider n jobs J_1, J_2 \dots J_n such that job J_i has execution time t_i and a non-negative integer weight w_i. The weighted mean completion time of the jobs is defined to be \frac{\sum_{i=1}^{n}w_iT_i}{\sum_{i=1}^{n}w_i}, where T_i is the completion time of job J_i. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?Q12.
The following circuit implements a two-input AND gate using two 2-1 multiplexers. What are the values of X_1, X_2, X_3?Q13.
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees ?Q14.
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.The automation which recognizes the language L(P)\capL(Q) is :Q15.
Consider the following DFA in which S_0 is the start state and S_1, S_3 are the final statesWhat language does this DFA recognize?Q16.
Consider the following two statements: i.A hash function (these are often used for computing digital signatures) is an injective function. ii.A. encryption technique such as DES performs a permutation on the elements of its input alphabet. Which one of the following options is valid for the above two statements?Q18.
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that ofQ19.
You are given the following four bytes : \begin{array}{|l|l|l|l|l|l|l|l|l|l|} \hline 10100011 & 00110111 & 11101001 & 10101011 \\ \hline \end{array} Which of the following are substrings of the base 64 encoding of the above four bytes?Q20.
Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct. i. if A \rightarrow \rightarrow B and A \rightarrow \rightarrow C then A \rightarrow BC ii. if A \rightarrow B and A \rightarrow C then A \rightarrow \rightarrow BC iii. if A \rightarrow \rightarrow BC and A \rightarrow B then A \rightarrow C iv. if A \rightarrow BC and A \rightarrow B then A \rightarrow \rightarrow C Exactly how many of the above implications are valid?